In order to improve the reliability of a communication network, various techniques have been studied which allow searching for disjoint paths that bypass a communication route in which a failure, such as a node failure or a link failure, has occurred.
For example, a method of searching a plurality of paths passing from a source node to a destination node in a network, for a pair of link-disjoint paths or for a pair of node-disjoint paths, was proposed in R. Bhandari, “Optical physical diversity algorithms and survivable networks”, Proceedings of the 2nd IEEE Symposium on Computer and Communication (ISCC '97), pp. 433-441, 1997).
FIG. 18 is a diagram illustrating an example of a path search method in which a pair of link-disjoint paths passing from source node 20 to destination node 25 is reconfigured in an optical network.
A path search apparatus searches a plurality of paths passing from the source node 20 to the destination node 25, for a first path having the minimum total link-cost among the plurality of paths (refer to [1] in FIG. 18), based on topology information (not depicted in FIG. 18) of a network, for example, the optical network. Here, in the initial state, all the links in the network are defined as bidirectional links in the topology information, and a link cost of a link is expressed as a signed integer beside the link, if needed, as depicted in FIG. 18. In the example of FIG. 18, the path search apparatus finds, as the first path, a path SP1 “source node 20-->node 21-->node 22-->destination node 25” that has the minimum total link-cost “3” among all the paths passing from source node 20 to destination node 25.
Next, the path search apparatus changes the topology information of the network so that the direction of each link connecting adjacent two nodes along the first path SP1 is reversed, and the sign of each link cost along the first path SP1 is reversed. Then, the path search apparatus searches, based on the changed topology information, the plurality of paths for a second path having the minimum total link-cost among the plurality of paths (refer to [2] in FIG. 18). In the example of FIG. 18, the search apparatus finds, as the second path, a path SP2 “source node 20-->node 24-->node 22-->node 21-->node 23-->destination node 25” that has the minimum total link-cost “7” among all the paths passing from source node 20 to destination node 25. In this way, it is possible to change the topology information so that the first path is not searched for as a path having the minimum total link-cost among the plurality of paths.
Last, the path search apparatus reconfigures a pair of link-disjoint paths passing from source node 20 to destination node 25 by removing links shared by both the two paths SP1 and SP2 (refer to [3] and [4] in FIG. 18). In the example of FIG. 18, the path search apparatus reconfigures a pair of link-disjoint paths: Path 1 “source node 20-->node 21-->node 23-->destination node 25” and Path 2 “source node 20-->node 24-->node 22-->destination node 25”, by removing the link connecting nodes 21 and 22 and using the remaining parts of the first and second paths.